package cn.hutool.core.dp;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * 折线抽稀算法实现
 */
public class DouglasPeucker {


    /**
     * Douglas-Peucker算法
     * @param points 坐标点集合
     * @param tolerance 限定值
     * @return
     */
    public static List<Point> douglasPeuckerReduction(List<Point> points, Double tolerance) {
        if (points == null || points.size() < 3) {
            return points;
        }

        int firstPoint = 0;
        int lastPoint = points.size() - 1;

        //首尾两点不能相同
        while (Objects.equals(points.get(firstPoint), points.get(lastPoint))) {
            lastPoint--;
            //如果最后点都相同到小于2了，构不成三个点，直接返回points
            if (lastPoint < 2) {
                return points;
            }
        }
        List<Integer> pointIndexsToKeep = new ArrayList<>();
        //默认添加首尾两点
        pointIndexsToKeep.add(firstPoint);
        pointIndexsToKeep.add(lastPoint);
        //递归计算
        douglasPeuckerReduction(points, firstPoint, lastPoint,
                tolerance,  pointIndexsToKeep);
        //返回集合
        List<Point> returnPoints = new ArrayList<>();
        Collections.sort(pointIndexsToKeep);
        for (int index : pointIndexsToKeep) {
            returnPoints.add(points.get(index));
        }

        return returnPoints;
    }

    /**
     * 递归计算每个点到线段的长度，并分段递归重复计算
     * @param points 点集合
     * @param firstPointIndex 首点
     * @param lastPointIndex 尾点
     * @param tolerance 限定值
     * @param pointIndexsToKeep 点集合下标
     */
    private static void douglasPeuckerReduction(List<Point> points, Integer firstPointIndex, Integer lastPointIndex, Double tolerance,
                                                List<Integer> pointIndexsToKeep) {
        if (firstPointIndex + 2 > lastPointIndex) {
            return;
        }
        Double maxDistance = 0.0;
        Integer indexFarthest = 0;
        //遍历每个点
        for (Integer index = firstPointIndex + 1; index < lastPointIndex; index++) {
            Double distance = perpendicularDistance
                    (points.get(firstPointIndex), points.get(lastPointIndex), points.get(index));
            //只寻找线段上最长的点
            if (distance > maxDistance) {
                //替换值
                maxDistance = distance;
                //记录下标
                indexFarthest = index;
            }
        }
        //确定最大值超过限定值且不为首点
        if (maxDistance > tolerance && indexFarthest != 0) {
            //记录最大距离的点的下标
            pointIndexsToKeep.add(indexFarthest);
            //分段计算 Startpoint-MaxDistance
            douglasPeuckerReduction(points, firstPointIndex,
                    indexFarthest, tolerance,  pointIndexsToKeep);
            //分段计算 MaxDistance-Lastpoint
            douglasPeuckerReduction(points, indexFarthest,
                    lastPointIndex, tolerance,  pointIndexsToKeep);
        }
    }

    /**
     * 求出点到两点的距离
     * @param firstPoint 线段的起点
     * @param lastPoint 线段的终点
     * @param point 计算的点
     * @return
     */
    public static double perpendicularDistance(Point firstPoint, Point lastPoint, Point point) {
        //(x1,y1),(x2,y2),(x3,y3)
        //Area=0.5∗|((x1∗y2+x2∗y3+x3∗y1)−(y1∗x2+y2∗x3+y3∗x1))|
        //bottom = |((x1-x2)²+(y1-y2)²)|
        //Area = 0.5*bottom*H
        //Height = Area/bottom*2
        //求面积
        double area = Math.abs(0.5 * (firstPoint.x * lastPoint.y + lastPoint.x *
                point.y + point.x * firstPoint.y - lastPoint.x * firstPoint.y - point.x *
                lastPoint.y - firstPoint.x * point.y));
        //求首尾两点的长度(底边的长度)
        double bottom = Math.sqrt(Math.pow(firstPoint.x - lastPoint.x, 2) +
                Math.pow(firstPoint.y - lastPoint.y, 2));
        //高
        double height = area / bottom * 2;

        return height;
    }

    public static class Point {
        double x;
        double y;

		public double getX() {
			return x;
		}

		public void setX(double x) {
			this.x = x;
		}

		public double getY() {
			return y;
		}

		public void setY(double y) {
			this.y = y;
		}

		@Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (!(obj instanceof Point)) {
                return false;
            }
            Point p = (Point)obj;
            return this.x == p.x && this.y == p.y;
        }

        @Override
        public String toString() {
            return "{" + x + "," + y + "}";
        }
    }
}
